/*
 * @lc app=leetcode.cn id=4 lang=golang
 * @lcpr version=30118
 *
 * [4] 寻找两个正序数组的中位数
 */

// @lcpr-template-start

// @lcpr-template-end
// @lc code=start
func findMedianSortedArrays(nums1 []int, nums2 []int) float64 {
	n, m := len(nums1), len(nums2)
	if n > m {
		nums1, nums2 = nums2, nums1
		n, m = m, n
	}
	imin, imax, half_len := 0, n, (n+m+1)/2
	for imin <= imax {
		i := (imin + imax) / 2
		j := half_len - i
		if i < n && nums2[j-1] > nums1[i] {
			imin = i + 1
		} else if i > 0 && nums1[i-1] > nums2[j] {
			imax = i - 1
		} else {
			max_of_left := 0
			if i == 0 {
				max_of_left = nums2[j-1]
			} else if j == 0 {
				max_of_left = nums1[i-1]
			} else {
				max_of_left = max(nums1[i-1], nums2[j-1])
			}
			if (n+m)%2 == 1 {
				return float64(max_of_left)
			}
			min_of_right := 0
			if i == n {
				min_of_right = nums2[j]
			} else if j == m {
				min_of_right = nums1[i]
			} else {
				min_of_right = min(nums2[j], nums1[i])
			}
			return float64(max_of_left+min_of_right) / 2.0
		}
	}
	return 0.0
}

// @lc code=end

/*
// @lcpr case=start
// [1,3]\n[2]\n
// @lcpr case=end

// @lcpr case=start
// [1,2]\n[3,4]\n
// @lcpr case=end

*/

